/* The algorithm is on introduction to algorithm */

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int HeapSize = 0;

/* adjust to make it a heap */
void MaxHeapify(int *a,int i)
{
	int l = 2*i, r = 2*i+1, largest;
	if( l<=HeapSize && a[l]>a[i] )
		largest = l;
	else largest = i;
	if(r<=HeapSize && a[r]>a[largest])
		largest = r;
	if(largest != i)
	{
		swap(a[i],a[largest]);
		MaxHeapify(a,largest);
	}
}

/* return the max element(that is the top of the heap) */
int HeapExtractMax(int* a)
{
	if(HeapSize<1)
	{
		cout<<"heap underflow!"<<endl;
		exit(0);
	}
	cout<<"heapsize = " <<HeapSize<<endl;

   	int	Max = a[1];
	a[1] = a[ HeapSize ] ;
 	HeapSize = HeapSize - 1;
	MaxHeapify(a,1);
	return Max;
}

void HeapIncreaseKey(int *a,int i , int key)
{
	if(key<a[i])
	{
		cout<<"new key is smaller than the current key"<<endl;
		exit(0);
	}

	/* replace the a[i] by key */
	a[i] = key;

	/* update the element to maintain the heap kind*/
	while(i>1 && a[i/2]<a[i])
	{
		swap(a[i],a[i/2]);
		i = i/2;
	}
}

void MaxHeapInsert(int *a,int key)
{
	HeapSize = HeapSize+1;
	a[HeapSize] = -100000;
	HeapIncreaseKey(a,HeapSize,key);
}

int main()
{
	int a[11]={0,0,6,7,8,3,4,2,5,9,1};

	/* Establish the Max heap by inserting element one by one  */
	for(int i=1;i<=10;i++)
		MaxHeapInsert(a,a[i]);

	/* Extract the maxmum element one by one */
	for(int i=1;i<=10;i++)
	{
		cout<<endl;
		cout<<"the elements in array  a = ";
		for(int j=1;j<=10;j++)
			cout<<a[j]<<" ";
		cout<<endl;
		printf("max = %d\n",HeapExtractMax(a));
		cout<<"the elements in heap are : ";
		for(int j=1;j<=HeapSize;j++)
			cout<<a[j]<<" ";
		cout<<endl;
	}

	return 0;
}





